package sfg;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedList;
import java.util.Queue;

import utils.Bitwise;
import dataStructure.Graph;
import dataStructure.Path;
import dataStructure.Graph.G_Path;
import fn.Add;
import fn.Constant;
import fn.Divide;
import fn.Function;
import fn.Multiply;
import fn.Subtract;
import gui.UI_Branch;
import gui.UI_Node;
import gui.UI_SFG;

public class Solver<N, B> implements Serializable {

	private static final long serialVersionUID = 3571572477641850888L;

	private static Solver solver;
	private Graph<N, B> graph;
	private int sourceNode, outPutNode;
	private ArrayList<Path<N>> forwardPaths;
	private ArrayList<Path<N>> loops;
	private ArrayList<ArrayList<ArrayList<Path<N>>>> nonTougching;
	private Function delta;
	private ArrayList<Function> deltas;
	private Function transferFunction;

	public static <N, B> Solver<N, B> get(Graph<N, B> g, N s, N o) {
		if (solver == null)
			solver = new Solver(g, s, o);
		return solver;
	}

	private Solver(Graph<N, B> g, N s, N o) {
		graph = g;
		sourceNode = g.getNodeHash(s);
		outPutNode = g.getNodeHash(o);
		solve();
		nonTougching = nonTouchingLoops(loops);
		delta = calcDelta(loops, nonTougching);
		deltas = calcDeltas();
		transferFunction = calcTransferFn();
	}

	private void solve() {
		forwardPaths = new ArrayList<Path<N>>();
		loops = new ArrayList<Path<N>>();
		Path<N> path = graph.createPath(sourceNode);
		Queue<Path> s = new LinkedList<Path>();
		s.add(path);
		int k = 0;
		while (!s.isEmpty()) {
			path = s.poll();
			if (path.end() == outPutNode)
				forwardPaths.add(path);
			for (int i = 0; i < graph.nNodes(); i++)
				if (graph.isConnected(path.end(), i))
					if (!path.isVisited(i))
						s.add(path.moveTo(i));
					else if (i <= path.end())
						loops.add(((G_Path) path.moveTo(i).adjust()).setName("L" + ++k));
		}
	}

	private ArrayList<ArrayList<ArrayList<Path<N>>>> nonTouchingLoops(ArrayList<Path<N>> loops) {
		ArrayList<ArrayList<ArrayList<Path<N>>>> nonTougching = new ArrayList<ArrayList<ArrayList<Path<N>>>>();
		for (int i = 0; i <= loops.size(); i++)
			nonTougching.add(new ArrayList<ArrayList<Path<N>>>());
		for (long i = 3; i < (1 << loops.size()); i++) {
			ArrayList<Path<N>> comb = combine(loops, i);
			if (!isTouching(comb))
				nonTougching.get((int) Bitwise.nOnes(i)).add(comb);
		}
		return nonTougching;
	}

	private ArrayList<Function> calcDeltas() {
		ArrayList<Function> deltas = new ArrayList<Function>();
		for (int i = 0; i < forwardPaths.size(); i++) {
			ArrayList<Path<N>> eliminated = eliminate(loops, forwardPaths.get(i));
			ArrayList<ArrayList<ArrayList<Path<N>>>> nonTouching = nonTouchingLoops(eliminated);
			deltas.add(calcDelta(eliminated, nonTouching));
		}
		return deltas;
	}

	private Function calcTransferFn() {
		Function tf = Constant.create(0);
		for (int i = 0; i < deltas.size(); i++)
			tf = Add.create(tf, Multiply.create(evaluatePath(forwardPaths.get(i)), deltas.get(i)));
		tf = Divide.create(tf, delta);
		return tf;

	}

	private Function calcDelta(ArrayList<Path<N>> loops, ArrayList<ArrayList<ArrayList<Path<N>>>> nonTougching) {
		Function delta = Constant.create(1);
		for (int i = 0; i < loops.size(); i++)
			delta = Subtract.create(delta, evaluatePath(loops.get(i)));

		for (int i = 0; i < nonTougching.size(); i++) {
			if (i % 2 == 0)
				for (int j = 0; j < nonTougching.get(i).size(); j++)
					delta = Add.create(delta, evaluatePath(nonTougching.get(i).get(j)));
			else
				for (int j = 0; j < nonTougching.get(i).size(); j++)
					delta = Subtract.create(delta, evaluatePath(nonTougching.get(i).get(j)));
		}
		return delta;
	}

	private ArrayList<Path<N>> eliminate(ArrayList<Path<N>> paths, Path<N> a) {
		ArrayList<Path<N>> eliminated = new ArrayList<Path<N>>();
		for (int i = 0; i < paths.size(); i++)
			if (!a.intersects(paths.get(i)))
				eliminated.add(paths.get(i));
		return eliminated;
	}

	public Function evaluatePath(Collection<Path<N>> p) {
		Function f = Constant.create(1);
		for (Path<N> path : p)
			f = Multiply.create(f, evaluatePath(path));
		return f;
	}

	public Function evaluatePath(Path<N> path) {
		int j = path.start();
		Function f = Constant.create(1);
		for (Integer i : path.path())
			f = Multiply.create(f, ((UI_Branch) graph.getConnection(j, j = i)).fn());
		return f;
	}

	private boolean isTouching(ArrayList<Path<N>> comb) {
		if (comb.size() == 1)
			return true;
		for (int i = 0; i < comb.size() - 1; i++)
			for (int j = i + 1; j < comb.size(); j++)
				if ((comb.get(i).visited() & comb.get(j).visited()) != 0)
					return true;
		return false;
	}

	private ArrayList<Path<N>> combine(ArrayList<Path<N>> loops, long i) {
		ArrayList<Path<N>> out = new ArrayList<Path<N>>() {
			@Override
			public String toString() {
				return super.toString().replaceAll("\\[ \\]", "").replaceAll(",", ".");
			}
		};
		int j = 0;
		do
			if ((i & 1) != 0)
				out.add(loops.get(j));
		while ((i >>= 1) != 0 && ++j != 0);
		return out;
	}

	public ArrayList<Path<N>> forwardPaths() {
		return forwardPaths;
	}

	public ArrayList<Path<N>> loops() {
		return loops;
	}

	public ArrayList<ArrayList<ArrayList<Path<N>>>> nonTouchingLoop() {
		return nonTougching;
	}

	public Function delta() {
		return delta;
	}

	public ArrayList<Function> deltas() {
		return deltas;
	}

	public Function transferFunction() {
		return transferFunction;
	}

	public static void main(String[] args) {
		UI_Node s, e;
		UI_SFG graph = new UI_SFG();
		graph.addNode(s = new UI_Node(null).setName("R(s)"));
		graph.addNode(new UI_Node(null).setName("X1"));
		graph.addNode(new UI_Node(null).setName("X2"));
		graph.addNode(new UI_Node(null).setName("X3"));
		graph.addNode(new UI_Node(null).setName("X4"));
		graph.addNode(e = new UI_Node(null).setName("C(s)"));
		graph.connect(0, 1, new UI_Branch(graph, null, null).setFn("1"));
		graph.connect(1, 2, new UI_Branch(graph, null, null).setFn("1"));
		graph.connect(2, 3, new UI_Branch(graph, null, null).setFn("1"));
		graph.connect(3, 4, new UI_Branch(graph, null, null).setFn("1"));
		graph.connect(4, 5, new UI_Branch(graph, null, null).setFn("1"));
		graph.connect(2, 1, new UI_Branch(graph, null, null).setFn("1"));
		graph.connect(3, 1, new UI_Branch(graph, null, null).setFn("1"));
		graph.connect(2, 5, new UI_Branch(graph, null, null).setFn("1"));
		graph.connect(3, 5, new UI_Branch(graph, null, null).setFn("1"));
		graph.connect(4, 3, new UI_Branch(graph, null, null).setFn("1"));
		graph.connect(5, 4, new UI_Branch(graph, null, null).setFn("1"));
		System.out.println(graph);
		get(graph, s, e);
	}
}